/**删除有序数组中的重复项-双指针
 * 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次,
 * 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
 *    更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。
 *    nums 的其余元素与 nums 的大小不重要。返回 k 。
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  // 输入：nums = [0,0,1,1,1,2,2,3,3,4]
  // 输出：5, nums = [0,1,2,3,4]
  if (nums.length === 0) return 0;
  let slow = 0;
  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast];
    }
  }
  return {
    slow: slow + 1,
    nums
  };
  return slow + 1;
};
// console.log(removeDuplicates([0, 0, 1, 1, 1, 2, 2, 3, 3, 4]));
console.log(removeDuplicates([0, 1, 2, 0, 1, 3]));

/**三数之和-双指针
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]]
 * 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 * 答案中不可以包含重复的三元组。
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
  // 1.先排序
  nums = nums.sort((a, b) => a - b);
  let res = [];
  // [-4,-1,-1,0,1,2]
  // 使用 nums.length - 2 是为了确保在遍历数组时，留出足够的空间给双指针（left 和 right）进行操作
  for (let i = 0; i < nums.length - 2; i++) {
    // 跳过重复的 i 值
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const num = nums[i] + nums[left] + nums[right];
      if (num === 0) {
        res.push([nums[i], nums[left], nums[right]]);
        // 考虑去重，相邻两数不要相同，相同时，指针继续移动
        while (nums[left] === nums[left + 1] && left < right) {
          left++;
        }
        while (nums[right] === nums[right - 1] && left < right) {
          right--;
        }
        left++;
        right--;
      } else if (num > 0) {
        right--;
      } else if (num < 0) {
        left++;
      }
    }
  }
  return res;
};

/**最接近的三数之和-双指针
 * 给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
 * 返回这三个数的和。
 * 假定每组输入只存在恰好一个解。
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  // 输入验证
  // if (!Array.isArray(nums) || !nums.every(Number.isFinite)) {
  //   throw new Error('Input must be an array of numbers');
  // }
  // 处理边界条件
  if (nums.length < 3) {
    return null; // 或者返回 undefined
  }
  // 1.先排序
  nums = nums.sort((a, b) => a - b);
  let res = Infinity; // 初始化一个最大值，先让差值最大
  // [-4,-1,-1,0,1,2] 0
  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      // 只要sum与target的绝对值比上次的res的绝对值小，就更新res
      if (Math.abs(sum - target) < Math.abs(res - target)) {
        res = sum;
      }
      if (sum < target) {
        left++;
      } else if (sum > target) {
        right--;
      } else {
        return sum;
      }
    }
  }
  return res;
};

/*盛最多水的容器-双指针
      给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
     * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
     * 返回容器可以储存的最大水量。
     * 注意：你不能倾斜容器。
     * 示例 1：
     * 输入：height = [1,8,6,2,5,4,8,3,7]
     * 输出：49
     * 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
     * @param {number[]} height
     * @return {number}
     */
var maxArea = function (height) {
  let maxArea = 0;
  let left = 0;
  let right = height.length - 1;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    maxArea = Math.max(maxArea, area);
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return maxArea;
};

/**移动零-双指针
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 * @param {number[]} nums
 * @return nums
 */
var moveZeroes = function (nums) {
  // 输入: nums = [0,1,0,3,12] 不是0就移动
  // 输出: [1,3,12,0,0]
  let left = 0;
  // 遍历数组
  for (let right = 0; right < nums.length; right++) {
    if (nums[right] !== 0) {
      // 交换非零元素到 left 指针位置
      [nums[left], nums[right]] = [nums[right], nums[left]];
      // left 指针右移
      left++;
    }
  }
  return nums;
};
// const nonZeroNums = nums.filter(num => num !== 0);
// // 计算零的个数
// const zeroCount = nums.length - nonZeroNums.length;
// // 填充非零元素
// for (let i = 0; i < nonZeroNums.length; i++) {
//   nums[i] = nonZeroNums[i];
// }
// // 在末尾填充零
// for (let i = nonZeroNums.length; i < nums.length; i++) {
//   nums[i] = 0;
// }
